package _11_整理题目._4_动态规划._接雨水;

import org.junit.Test;

/**
 * https://leetcode-cn.com/problems/volume-of-histogram-lcci/
 *
 * 给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
 *
 * 思路一：暴力计算
 *      两边的位置不能接水，中间的位置 i 接水量 = 左右最大高度中的 较小值 - 当前高度
 *      可以遍历数组，暴力计算每个位置的左右最大高度，然后计算
 *
 * 思路二：动态规划，时间 O(n)，空间 O(n)
 *      使用动态规划 遍历三次
 *      先计算出每个位置的 左右最大高度，new 一个 leftMax[]  rightMax[]
 *      leftMax[0] 初始值 height[0]，leftMax[i] = Math.max(leftMax[i-1], height[i]);
 *      然后反向遍历 计算 rightMax
 *      最后通过 Math.min(leftMax[i], rightMax[i]) - height[i] 计算每个位置 i 接水量*
 *
 * 思路三：双指针，时间 O(n)，空间 O(1)
 *
 */
public class _01_一维数组接雨水 {

    // 动态规划
    public int trap(int[] height) {
        int n = height.length;
        if (n < 3) return 0;
        
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i-1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n-1] = height[n-1];
        for (int i = n-2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i+1], height[i]);
        }

        int ans = 0;
        for (int i = 1; i <= n-2; i++) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return ans;
    }

    @Test
    public void main() {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height));
    }

}
